

public class ExerciseSort {
    //第四次练习  直接插入排序法    i从1开始移动，找到i前面比较小的值
    //时间复杂度：n^2  空间 1  稳定
    public static void insertSort4(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= 0 ; j--) {
                //小数往前走
                if(array[j] > tmp ) {
                    array[j + 1] = array[j];
                } else {
                    array[j + 1] = tmp;
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }


    //第四次练习直接排序法 ,把后面的最小值跟最前面的值进行交换
    //时间复杂度：O（N^2）  空间复杂度O（1）  不稳定
    //i从0开始，找到后面最小的值，放到最前面
    public static void selectSort4(int[] array) {
        for (int i = 0; i < array.length; i++) {
            //int tmp = array[i];
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if(array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            swap(array,minIndex,i);
        }
    }

    //交换函数 进行封装起来
    private static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    /**
     * 快排法
     * 时间复杂度：O(N * log N)
     * 空间复杂度：树的高度 log N， 最坏情况下是单树N
     * 不稳定
     * @param array
     */


    public static void quickSort2(int[] array) {
        quick2(array,0,array.length - 1);  //给下标
    }
    public static void quick2(int[] array,int start,int end) {
        if(start >= end ) {
            return;
        }
        //三数取中法
        int index =midThree(array,start,end);
        swap(array,index, start);


        int privo = partition4(array,start,end);
        quick2(array,start,privo - 1);
        quick2(array,privo + 1,end);
    }

    private static int midThree(int[] array,int left,int right) {
        int mid = (left+right) / 2;
        //6  8
        if(array[left] < array[right]) {
            if(array[mid] < array[left]) {
                return left;
            }else if(array[mid] > array[right]) {
                return right;
            }else {
                return mid;
            }
        }else {
            //array[left] > array[right]
            if(array[mid] < array[right]) {
                return right;
            }else if(array[mid] > array[left]) {
                return left;
            }else {
                return mid;
            }
        }

    }
    //hoare法
    public static int partition4(int[] array,int left,int right) {
        int ret = left;
        int tmp = array[left];
        while(left < right) {
            //int tmp = array[left];   注意此处必须放在上面，因为left在发生变化，而我们要求比较的一直是左边那个
            while(left < right && array[right] >= tmp) {
                right--;
            }
            while(left < right && array[left] <= tmp) {
                left++;
            }
            swap(array,left,right);
        }
        swap(array,left,ret);
        return left;
    }

}
